/*
 * @lc app=leetcode.cn id=51 lang=typescript
 *
 * [51] N 皇后
 */

// @lc code=start
function solveNQueens(n: number): string[][] {
  // 初始化棋盘
  const board = new Array(n).fill('.').map(() => new Array(n).fill('.'));
  const backtrack = (idx: number) => {
    // 最后一行，代表有合法数据，更新结果
    if (idx === n) {
      const result = new Array(n).fill('.');
      for (let i = 0; i < board.length; i++) {
        result[i] = board[i].join('');
      }
      ans.push(result);
      return;
    }
    // 遍历每一列
    for (let j = 0; j < n; j++) {
      if (visitedCol.has(j)) continue;
      if (visitedDiagonal.has(idx - j)) continue;
      if (visitedBackDiagonal.has(idx + j)) continue;
      // 选择当前位置
      board[idx][j] = 'Q';
      visitedCol.add(j);
      visitedDiagonal.add(idx - j);
      visitedBackDiagonal.add(idx + j);
      // 继续选择下一行
      backtrack(idx + 1);
      // 回溯到上一个位置
      board[idx][j] = '.';
      visitedCol.delete(j);
      visitedDiagonal.delete(idx - j);
      visitedBackDiagonal.delete(idx + j);
    }
  };
  // 存在皇后的列
  const visitedCol: Set<number> = new Set();
  // 存在皇后的对角线
  const visitedDiagonal: Set<number> = new Set();
  // 存在皇后的反对角线
  const visitedBackDiagonal: Set<number> = new Set();
  const ans = [];

  backtrack(0);

  return ans;
}
// @lc code=end
